原题链接：https://www.acwing.com/problem/content/1136/
题目大意：
给你一个n个点，m条边的无向无权图。问从起点开始，到每个点的最短路有几条。
输出所有点的条数，并对取模，如果无法到达则输出0。
数据范围：
假如说这个图是个DAG且无权，似乎就非常好做了。在这种情况下直接去统计每个点被更新的点各有几条最短路加和就行了。但是这是一个无向图，联系最短路，我们发现可以构造出一个特殊的图来：
对每个点，链接与更新了他的距离的所有点连边，我们可以获得一个DAG。
证明：反证法，假设获得的图不是一个DAG，那么必然存在一个点他往回走且获得了更小的距离，形成了环形依赖。也就是说出现了下图这种连回去的情况
但是整个图是无权图，每个边的边权都是，因此绕一圈一定不可能是新的最短路，故这样构造出来的图一定是一个DAG。
有了这个构造出来的图（记作），就可以实现我们之前的美好愿望了。但是状态的累积也不能随便累积，比较直接的一个想法就是去结合一下最短路算法，在这个图上跑最短路再顺便计数。
首先BFS是正确的，我们来想一下这个过程应该是怎么样的，对于某个点来说：
①是只会被缩短一次的，之后一定就是最短距离了。
②因为拓展一次之后就是最短距离，如果此后还有其他点连向了，那么距离是不会变得更小的。不可能有一个新的点连通向使得变得更小，这保证了：我们在搜到最短路之后，只要距离相同就累加这样做是正确的，因为不会说中途出现一个新的点使距离变小，前面的计数全部作废了。
③按上面的分析，新的点连通过来进行更新的话，最多与之相同，那么在相同的时候说明这也是一条最短路，累加进去就好。
综上，通过更新最短路条数是正确的。
那么其他的最短路算法是不是正确的，下个问题里再细说。
代码：https://www.acwing.com/activity/content/code/content/366823/
有关次短路的拓展
原题链接：https://www.acwing.com/problem/content/385/
题目大意：给定一个有向带权图，和起点/终点，问从起点到终点的最短路和恰好只比最短路长度多的条数。数据保证结果不超过
数据范围：
先不管次短路的问题，想一想这个题与上面那个题有什么区别。
为什么上一个题可以直接去做呢，因为上一个题是无权图，他里面每一个点权都是，每次拓展的时候就一定是最短的，但是这个题不行，因为带权了。不过带权我们自然想到和，那么他俩好像也可以在这里处理。
结论是：和都可以做，但是前者是可以像上面那一题直接去做的，后者不行。
回忆一下上一个题的正确性是怎么保证的：
①每个点只会被拓展一次
②每个点第一次拓展之后就一定是最短距离了
我们发现很显然是满足的，但是是不满足的，因为对于来说，第一次拓展完某一个点之后不一定就是最短距离了，可能还需要经过多次拓展才行。假如说这个图里有负权，只能用怎么办，只要先对图跑一次普通的求出最短路再计数就可以了。其次如果图里有负环，那么连最短路都不存在了，也需要特殊对待一下。
回到这题来，这个题除了带边权这个拓展以外，还多了一个求次短路的问题，就是说如果次短路恰好比最短路多的话也要计入答案里去。既然最短路的拓展是不会有环形依赖的，那么次短路是不是也一样的呢？结论是正确的，留给读者证明。得到这个结论之后，只要仿照上面的简化版去更新最短路和次短路顺便计数就可以了。
但是这道题具体实现上还有一个问题：一个点既可以是由最短路拓展而来，也可以是由次短路拓展而来，也就是说他有可能合法地，注意是合法地出队两次，那这个时候我就根本搞不清楚他该不该跳过了，原来是最短路的时候我直接判断是不是就过去了，这里不行，因为次短路拓展过来的一个点可能后面还会有一个更优的次短路存在，所以这里用到一个拆点的思想：我们把每个状态额外增加一个表示它是一个最短的还是一个次短的，判重出队的时候，同样的把判重数组等等一系列信息都拓展成两维的，也就是说对于某个点来说我们判他是最短路出一次，次短路出一次，重复了就跳过，这样就解决了这个问题。
本题细节相当多，也有相当的难度，而且我写题解还写得不咋地，如果有理解问题看下面代码：
https://www.acwing.com/activity/content/code/content/367292/